This invention relates to a method for virtual enlargement of the data structure of a fast read-write memory on a portable data carrier, and relates further to a portable data carrier with a microcontroller consisting at least of a processor, an I/O unit, a fast read-write memory with a stack, a slow read-write memory, an operating system and at least one data, control and address bus.
Portable data carriers are known e.g. in the form of smart cards. The latter are characterized in that they have an integrated circuit incorporated in the card body and equipped with means for data transfer and storage and with a unit for processing said data. To protect the chip from damage by breakage or torsion and for security reasons the area of the chip is kept small. It has proved advantageous in practice to choose a square area of 25 mm2 if possible. The chip located on the smart card with all its modules, in particular its memory modules, is therefore greatly restricted in its superficial extent.
Due to this restricted extent and with consideration of the type-dependent different amount of space required by the different memory chips—a 1-bit memory cell of a RAM requires about four times as much space as a 1-bit memory cell of an EEPROM, while the latter in turn requires four times as much as a 1-bit cell of a ROM—it is necessary to try and avoid using the area-intensive memory chips, i.e. in particular the RAM chips, and instead choose less area-intensive chips, such as an EEPROM or ROM. However, in order not to have to accept any functional losses from the desirable replacement of an area-intensive chip by a less area-intensive different one, the functionality of the originally used chip must be maintained.
Smart cards have a great variety of fields of application and purposes. Thus, so-called memory cards are used primarily as telephone cards or health insurance cards. Their functionality is limited to a specific application. Microprocessor cards, however, are characterized by an additional block of modules containing a CPU. Usually, these cards also have along with the CPU an I/O unit, a data, control and address bus, a volatile read-write memory (RAM), a nonvolatile read-write memory (EEPROM) and a a nonvolatile read-only memory (ROM). The operating system is stored mainly in the ROM.
In dependence on whether they access further programs besides the operating system, the cards are either designed only for one specific application stored in the ROM or can perform different tasks specified in the further user programs. This distinctly increases the functionality of the cards. With this gain in functionality, however, the demand for memory space also rises. For example, more registers for the data to be processed and more return addresses for the great number of subprograms must be provided in the RAM. In the cards common at present, however, the relevant area of the RAM, namely the area organized as a stack, is insufficient for more complex applications. Since the memory space of the area-intensive RAM chip cannot be expanded at will, as set forth above, the RAM limits the possible functionality range of the smart cards.
Newer smart cards have operating systems that permit reloading of executable program code. With this type of card, an application provider itself can execute with the smart card a program code that the operating system manufacturer does not know. So-called Java cards, for example, are based on programming in the language JAVA and on a so-called “Java virtual machine,” which is a simulation of a Java processor that can be implemented on any sufficiently powerful processor. Java cards are thus platform-independent to a very large extent. However, Java has a high stack requirement due to the necessary virtual machine. The limited physical size of the RAM therefore limits the possibilities of the Java card.
DE 196 26 337 A1 discloses a method and apparatus for reading and processing messages from the outside world to be processed on a smart card. Messages to be processed that are received via the I/O unit can have a size that cannot be written completely to the RAM because of the memory space limitation. For security reasons, messages from outside must moreover be subjected to access authorization control by the CPU before they can be processed. A simple division of the messages into blocks of smaller size would make authentication unnecessarily elaborate and delay it. So that communication with the smart card is to a very large extent independent of the data size of the messages despite the RAM being too small, messages from outside are either stored directly in the EEPROM or indirectly in the EEPROM subsequent to intermediate storage in the RAM. The proposed solution is based on the approach of creating possibilities of intermediate storage for messages, or data, that cannot be stored completely in the RAM due to their size. The virtual memory enlargement is effected via the I/O buffer of the RAM, i.e. via the optionally writable part of the RAM. This print contains no hint of enlarging that area of the RAM that is organized as a stack.
EP 720 087 discloses the proposal to virtually enlarge a hardware stack by setting up an expansion memory. The expansion memory is to be set up in a defined area of the RAM. The oldest stack entries are moved to the expansion memory when the fill state of the hardware stack exceeds a limiting value that is just under the maximum capacity of the hardware stack. When the limiting value is reached the oldest stack entry is moved to the expansion memory. If the limiting value is still reached, the next-oldest stack entry is then also moved out. This known method ensures that the hardware stack is always at least almost completely usable so as to permit effective memory utilization. This distinguishes it from another known concept by which the hardware stack is divided into sectors and at each subroutine call a new sector is used through a sector rotation, a sector being moved to a memory if all sectors are occupied.
The method disclosed in EP 720 087 is not transferable to portable data carriers, however, because demand swapping of individual stack entries requires a fast memory and must therefore necessarily be implemented in the RAM. There is not enough space for this in the RAM on portable data carriers, specifically on smart cards.
The stack has a special organization in contrast to the other areas in the RAM. It constitutes a data structure that is implemented as a LIFO data structure (last in, first out) and fundamentally permits simpler management and access algorithms than the other memory areas of the RAM, which are randomly accessed. Swapping parts of the stack can therefore meet different criteria from those applicable with respect to the other part of the RAM.
The RAM of smart cards freely programmable in high level language is limited at present by the—still—customary 8-bit controller and typically includes 256 bytes of internal IRAM and 1600 bytes of extended XRAM that is addressable via address computations and therefore slightly slower. The IRAM is normally used completely as a stack, while the XRAM contains the working memory and the I/O buffer.
The problem of the present invention is therefore to provide a method that permits virtual enlargement of the area of the RAM organized as a stack for a portable data carrier, in particular in the form of a smart card, so as to also permit execution of applications that would require a physically larger stack than is provided physically on the data carrier—while retaining the original computing power as completely as possible and adaptively taking account of the particular current system requirements—like the application software—and system balancing properties—like the access times to RAM and EEPROM, life of the EEPROM, etc.
A further problem is to provide a portable data carrier permitting execution of complex applications, in particular Java applets, that require an extended stack.
This problem is solved by a method having the following steps:    a) segmenting the stack into at least two stack segments,    b) detecting a fill parameter that describes a fill state for the stack,    c) monitoring the fill parameter by comparing the fill parameter detected in step b) with a predetermined limiting value,    d) swapping at least one stack segment to a further storage medium as soon as a predetermined relation between limiting value and fill parameters is reached.
Further, the problem is solved by a smart card wherein the operating system has means for segmenting the stack and swapping at least one segment of the RAM to a further memory, in particular to a nonvolatile read-write memory such as an EEPROM.
The stack is usually implemented as a LIFO data structure so that the last entry is processed first. Besides return addresses of subprograms, it contains local variables. The program stack is a stack in which the particular return addresses of the subprograms are stored at the call of subprograms. Upon execution of the program, the particular return addresses and the local variables of the subprogram are stored successively. In reverse order they are then required when the particular subprogram returns to the master program. Very old stack contents or return addresses occupy the stack memory space but are not currently required for executing the particular program. Therefore, blocks or segments of stack cells can be swapped to another, slower memory, for example the EEPROM. Only just before the current program must return to the higher program, the particular stack memory contents must be available again and are optionally swapped in again from the other storage medium. In the meantime the memory space of these stack cells can be used according to the invention for other records to be stored, e.g. for further return addresses and local variables. This method permits the stack to undergo virtual enlargement.
The invention exploits the fact that specifically the stack must expediently undergo virtual enlargement to permit the RAM to be most efficiently relieved as a whole. Due to the specific organization of the stack, an inventive swapping mechanism is applicable more effectively than in the memory areas of the RAM that are organized differently or not at all. If areas of the buffer were swapped, for example, higher access times to the swapped contents in the slower memory would have to be expected, since it is not foreseeable when which swapped buffer memory contents must be available in the RAM again when the latter is randomly accessed. It cannot be excluded that precisely the contents of the swapped cells must be available in the RAM again for the program run shortly after their swap. This results in a higher number of time-consuming accesses to the EEPROM. It can expediently be provided that the point of time for “being available in RAM” is precalculated when stack contents are swapped. This is possible due to the organization of the stack as a LIFO data structure.
An advantageous embodiment of the invention consists in the segmentation being done in powers of two 2n-m, where m=1, 2, 3 . . . 2m is the number of segmentations and 2n is the size of the stack according to memory cells or bytes. The dimension figure m for division is advantageously chosen so as to obtain optimal balancing o the smart card system, i.e. to take account of parameters stack, time for swapping segments in and out, additional o like size of the stack, time for swapping segments in and out, additional overhead for segment transfer, demand for stack memory space, etc., for the current application of the smart card. Segmentation is thus advantageously chosen based on parameters of the smart card system and in dependence on the application software, such as size, number of subprograms, etc. In a preferred segmentation, the segment size corresponds precisely to the size of the blocks of the EEPROM.
It thus results, for example, that a division or segmentation of the stack into two parts is most expedient for a first certain use of the smart card, so that the smart card system as a whole can guarantee an optimized run. For a further certain use of the smart card, a segmentation into several, smaller segments can be wiser, since this might for example obtain optimal system balancing more easily.
Advantageously, the inventive method also permits execution of smart card applications that require an especially large stack area, for example programs containing complex cryptographic algorithms or cards with Java applets. Here, users have the possibility of loading their specific programs onto the card. This advantageously increases the functionality of the card and its life, since e.g. program updates can be loaded onto the card.
In an alternative embodiment of the invention the lowest stack segment is not swapped to the EEPROM but to another nonvolatile read-write memory, such as a flash EEPROM or a FRAM (ferroelectric random access memory) or to an additional volatile read-write memory, for example a RAM, that is surface-optimized but thus has slower access times.
In one embodiment, in particular disadvantages in terms of time when swapping stack segments from the RAM with very fast access times to the EEPROM memory with substantially higher access times are avoided by previously preparing a stack balance. Thus, a segment is only swapped when a positive final balance results with consideration of the higher access times in relation to the stack area becoming free. To pre-prepare the stack balance, the application software can be tested on a simulator or a data flow analysis performed.
The choice of segmentation of the stack in powers of two 2n-m results in the advantage that the fill parameter can be coded in a minimal number, namely (m), of address bits. This means that in case of a division into two, i.e. m=1, one address bit suffices to mark and recognize the change from one stack segment to the next. With a division of the stack into four parts, i.e. m=2, only two address bits are required.
FIG. 1 indicates schematically portable data carrier 10 for which the form of a smart card will be assumed hereinafter. Smart card 10 bears microcontroller 32 consisting of processor 12, I/O unit 14, volatile read-write memory 16, in particular in the form of RAM 16 (random access memory), nonvolatile read-write memory 18, in particular in the form of EEPROM 18 (electrical erasable programmable read-only memory), nonvolatile read-only memory 20, in particular in the form of ROM 20 (read-only memory), operating system 22 stored in memories 18 and 20, and data, control and address bus 24. Each memory 16, 18, 20 includes a multiplicity of 1-bit memory cells whose physical size depends on the type of memory.